#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
char s[1000100];
int nt[1000100];
int len;
void getnt()
{
	nt[0] = -1;
	int i,t;
	i = 0,t=-1;
	while(i<len)
	{
		if(t==-1||s[i]==s[t])
		{
			t++;
			i++;
			
 			nt[i] = t;
			
		}
		else
		{
			t = nt[t];
		}
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
	
		scanf("%s",s);
		len = strlen(s);
		getnt();
		int l = len-nt[len];
		if(len%l==0&&l!=len) printf("0\n");
		else 
		{
			printf("%d\n",l-len%l);
		}
	}
}
